- Title
- Practical k nearest neighbor queries with location privacy
- Creator
- Yi, Xun; Paulet, Russell; Bertino, Elisa; Varadharajan, Vijay
- Relation
- 2014 IEEE 30th International Conference on Data Engineering . Proceedings of the 2014 IEEE 30th International Conference on Data Engineering (Chicago, IL 31 March - 4 April, 2014) p. 640-651
- Publisher Link
- http://dx.doi.org/10.1109/ICDE.2014.6816688
- Publisher
- Institute of Electrical and Electronics Engineers (IEEE)
- Resource Type
- conference paper
- Date
- 2014
- Description
- In mobile communication, spatial queries pose a serious threat to user location privacy because the location of a query may reveal sensitive information about the mobile user. In this paper, we study k nearest neighbor (kNN) queries where the mobile user queries the location-based service (LBS) provider about k nearest points of interest (POIs) on the basis of his current location. We propose a solution for the mobile user to preserve his location privacy in kNN queries. The proposed solution is built on the Paillier public-key cryptosystem and can provide both location privacy and data privacy. In particular, our solution allows the mobile user to retrieve one type of POIs, for example, k nearest car parks, without revealing to the LBS provider what type of points is retrieved. For a cloaking region with nxn cells and m types of points, the total communication complexity for the mobile user to retrieve a type of k nearest POIs is O(n+m) while the computation complexities of the mobile user and the LBS provider are O(n + m) and O(n2m), respectively. Compared with existing solutions for kNN queries with location privacy, our solutions are more efficient. Experiments have shown that our solutions are practical for kNN queries.
- Subject
- query processing; communication complexity; data privacy; mobility management; pattern recognition; public key cryptography
- Identifier
- http://hdl.handle.net/1959.13/1355892
- Identifier
- uon:31555
- Identifier
- ISBN:9781479925551
- Language
- eng
- Reviewed
- Hits: 2619
- Visitors: 2938
- Downloads: 0
| Thumbnail | File | Description | Size | Format |
|---|